#pragma once
#include<vector>
#include<iostream>
#include<iterator>
using namespace std;

class Search
{
private:
	template<class T>
	int sequenceSearch(vector<T>nums,T key) {
		for (int i = 0; i < nums.size(); i++) {
			if (nums[i] == key) 
				return i;
		}
		return -1;
	}

	template<class T>
	int binarySearch(vector<T>nums, T key) {
		int low = 0, high = nums.size() - 1;
		int mid;
		while (low <= high) {
			mid = (low + high) / 2;
			if (nums[mid] == key) {
				return mid;
			}
			if (nums[mid] > key) {
				high = mid - 1;
			}
			if (nums[mid] < key) {
				low = mid + 1;
			}
		}
		return -1;
	}

	template<class T>
	int insertSearch(vector<T>nums, T key) {
		int low = 0, high = nums.size() - 1;
		int mid;
		while (low <= high) {
			mid = low + (key - nums[low]) / (nums[high] - nums[low])*(high - low);
			if (nums[mid] == key) {
				return mid;
			}
			if (nums[mid] > key) {
				high = mid - 1;
			}
			if (nums[mid] < key) {
				low = mid + 1;
			}
		}
		return -1;
	}

public:
	Search();
	~Search();

	template<class T>
	int SequenceSearch(vector<T> nums, T key) {
		return sequenceSearch(nums, key);
	}

	template<class T>
	int BinarySearch(vector<T> nums, T key) {
		return binarySearch(nums, key);
	}

	template<class T>
	int InsertSearch(vector<T> nums, T key) {
		return insertSearch(nums, key);
	}
};

